package com.zhulei.biji.suanfa.pace;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @description:
 * @author: zhulei
 * @create: 2025-04-07 18:09
 **/
public class CanPartition {
    /**
     * 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
     *
     * 示例 1：
     *
     * 输入：nums = [1,5,11,5]
     * 输出：true
     * 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
     * 示例 2：
     *
     * 输入：nums = [1,2,3,5]
     * 输出：false
     * 解释：数组不能分割成两个元素和相等的子集。
     * 提示：
     *
     * 1 <= nums.length <= 200
     * 1 <= nums[i] <= 100
     * Related Topics
     * 数组
     * 动态规划
     *
     * 👍 2315
     * 👎 0
     */
    public static boolean canPartition(int[] nums) {
        long total = 0;
        for (int i = 0; i < nums.length; i++) {
            total = total + nums[i];
        }
        if (total % 2 != 0)
            return false;
        long half = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                if (half + nums[j] > total/2){
                    continue;
                }
                if (half + nums[j] == total/2){
                    return true;
                }
                if (half + nums[j] < total/2){
                    half = half + nums[j];
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(Integer.toBinaryString(Byte.MAX_VALUE));
    }

    public int countPairs(int[] nums, int k) {
        int reuslt = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if ((i*j)%k==0 && nums[i]==nums[j])
                    reuslt++;
            }
        }
        return reuslt;
    }
}
